Loading AI tools
来自维基百科，自由的百科全书
在图论中，细分（subdivision）或分割[2]是指在一个图的其中一条边加入新的顶点，使这条边转变成由多个顶点构成之路径的变换，又称为扩展（expansion）[3]，为图子式理论中的基本算子之一，而变换完的像称为细分图[5]。
在图论的一般情况下，细分通常是指对边的细分，而在一些领域中会有对面或其他结构的细分（如高维度的标记），例如重心细分[6]，有时会称为剖分及剖分图。
细分是一种作用于边上的变换，因此其需作用于特定的边，令其记为e，并令e所连接的两个顶点记为u和v，而细分会在顶点u和v之间加入一个新的顶点w，并使原本的边uv改成路径uwv则完成一次细分变换，换句话说，即先在uv边之间加入顶点w，移除uv边后将u和v连到w[5]。
例如现在有一条边，记作e，其由顶点u和v组成，记为{u,v}：
|
透过细分变换，产生了新的顶点w，将e分割成两条边，分别记为e1和e2，皆连到新顶点w：
|
而细分变换存在逆变换，称为平滑（smoothing）变换。
|
|
细分变换的结果套用平滑变换会形成原像：
|
|
更广义的，细分变换不一定只加入一个顶点，只要在边上有加入顶点的动作，都是一种细分，更精确地说，细分变换可以定义为将图G中的某一条边e替换为具有相同端点之路径，且构成该路径的顶点皆不在原本属于图G的顶点之中，且此路径也不会跟其他现有的顶点相连[7]。
假设有二图G和H，若图H可以透过反复对图G套用细分变换而得，则图H可以称为图G的细分图[5]。
当G'是G的细分时，则G'称为G的细分图，亦可以将G'称为G的扩展，记为TG，其中T表示扩展变换。G的原有的顶点若其位于细分作用的边上时，称为TG的分支顶点（branch vertex），在细分作用的边上加入之新的顶点称为TG的细分顶点（subdivision vertex），细分后产生的边称为细分边（subdivision edge）[8]，并且细分顶点具有度为2的特性[9]。
细分的概念应用于图论，最早出现在1930年波兰数学家卡齐米日·库拉托夫斯基提出的一类禁用准则（指满足某种条件的图就一定无法具有某个性质）中，其所提出的库拉托夫斯基定理使用了细分图的概念[2]。
细分可以用于几个与图论相关的证明和定理，例如判断两图是否同胚以及库拉托夫斯基定理中，对于简单图是否为平面图的准则，该定理为：如果一个简单图并不包含一个是 K5 或 K3,3 之细分图的子图，则该简单图是平面图，反之亦然，上述两条件为当且仅当关系[2]。其中， K5 代表有 5 个点的完全图，K3,3 代表两部分各 3 个点的完全二分图，特别地，若一图的子图是K5或 K3,3之细分图，则该子图又称为库拉托夫斯基子图[10] 。
细分变换在图论中有一些不同的定义，例如重心细分在图论中就不是将多边形分割成三角形。
在图论中，重心细分（Barycentric subdivision）是指将图的所有边进行细分的变换[11]，为一种特殊的细分变换，其变换的像总会是二分图[12]，且是一个无回路图[1]，而任何无回路图的重心细分结果皆会是简单图[1]。
重心细分可以被重复套用，任何图只要重复套用2次重心细分后结果总是简单图[11]。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
